package offer.binarytree;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/20 21:09
 */
public class PostOrderJudge24 {

    /**
     * @param list
     * @param start 下标，从零开始
     * @param end   下标，从0开始
     * @param <T>
     * @return
     */
    public static <T extends Comparable<? super T>> boolean isPostOrderList(T[] list, int start, int end) {
        if (list == null || list.length <= 0 || start > end || start < 0 || start >= list.length || end < 0 || end >= list.length)
            return false;
        if (start == end)
            return true;
        T head = list[ end ];

        int i = start;
        for (; i < end; i++) {
            if (list[ i ].compareTo(head) > 0)
                break;
        }

        for (int j = i; j < end; j++) {
            if (list[ j ].compareTo(head) < 0)
                return false;
        }

        boolean leftMatch = isPostOrderList(list, start, i - 1);
        boolean rightMatch = isPostOrderList(list, i, end - 1);

        return leftMatch && rightMatch;

    }


    public static <T extends Comparable<? super T>> boolean isPostOrderList(T[] array){
        return isPostOrderList(array,0,array.length-1);
    }


    public static boolean VerifySquenceOfBST(int [] sequence) {
        return VerifySquenceOfBST(sequence,0,sequence.length-1);
    }

    private static boolean VerifySquenceOfBST(int [] sequence,int low,int high){
        int div;
        if(low >= high)
            return true;
        else{
            div = low;
            while(sequence[div] < sequence[high])
                div++;
        }
        for(int i = div;i < high;++i)
            if(sequence[i] < sequence[high])
                return false;
        boolean left = VerifySquenceOfBST(sequence,low,div-1);
        boolean right = VerifySquenceOfBST(sequence,div,high-1);
        return left && right;
    }

    public static void main(String[] args) {
        int[] array = {4,6,5,7};
        System.out.println(VerifySquenceOfBST(array));
    }



}
